HW#5 --- last modified February 07 2019 04:30:05..

Solution set.

Due date: May 12

Files to be submitted:
  Hw5.zip

Purpose:

The main course outcomes covered by this assignment are:

LO2 -- Prove basic properties of trees and graph

LO3 -- Perform breadth-first search and depth-first search on directed as well as undirected graphs.

LO7 -- Comprehend the basic concept of NP-completeness and realize that they may not be able to efficiently solve all problems they encounter in their careers.

LO8 -- Comprehend algorithms designed using greedy, divide-and-conquer, and dynamic programming techniques.

Specification:

For this homework there will be two parts: a written part and a coding part. Both parts of the homework should be submitted in your Hw5.zip file which must be submitted using the online submission system. For the written part I want you to do the following problems below, and put your solutions into a file Hw5.pdf (no Word docs please!) which you put in your zip file. Put your name and ID clearly on the front page of this file.

1. Let +i denote "insert item i into a red-black tree using the book's (or class') code"; let -i denote "delete item i into a red-black tree using the book's (or class') code". Show the RB-trees that result after each operation in the following sequence of inserts and deletes: +1 +4 +7 +10 -4 +2 +5 +8 +11 -8 +3 +6 +9 +12.
2. Consider the two sequences: `langle 0, 1, 0, 0, 1, 0, 1 rangle` and `langle 1, 1, 0, 1, 0, 0, 1, 1, 0 rangle`. Give the tables that would be constructed by the LCS-length procedure. Then show step-by-step how PRINT-LCS would use these table to build a longest common sub-sequence.
3. Consider the instance of the activity-selector problem given by the table below:

   i	1	2	3	4	5	6	7	8
   `s_i`	2	3	0	4	5	7	8	2
   `f_i`	5	6	7	7	8	10	11	11

   Show how the greedy recursive algorithm, RECURSIVE-ACTIVITY-SELECTOR, solves this problem.
4. Prove that the Knapsack problem discussed in class is in NP. Here a Knapsack instance consists of a set of a table of items sizes s(1), ..., s(n); a table of values of each item v(1), ..., v(n), a knapsack size `m` and a goal value `k`. An instance is in Knapsack if this is a subset of the items such that the sum of their sizes is less than `m` and the value of these items is greater than `k`.

For the coding part of the assignment you will code a program TopSort.java. The grader will compile your code by typing the following at the command line:

javac TopSort.java

Your code will be run from the command line with a line like:

java TopSort l1 r1 l2 r2 l3 r3 ... ln rn

For example,

java TopSort 1 2 2 3 3 1

The input above would represent the graph with edge (1,2), (2,3), (3, 1). i.e., each pair of positive integers listed represents one edge. You can assume the inputs will always be positive integers and you are not required to do error checking. On such an input your code should first determine the largest input vertex number, in this case, 3. Your code should use this so it can make the array of linked-lists needed for the adjacency-list representation of the graph. Your code should then out put the linked-list of vertices that would have been gotten by running the book/classes's pseudo-code (which uses the adjacency list representation of graph) for topological sort on the given graph. In this case the output would be:

1 2 3
Has Cycle

Notice in the above input, the graph was a cycle, so it is not topologically sortable. So at some point in DFS(G) a back edge must have been detected. I want you to modify DFS(G) so that it remembers if a back edge was found and either output No Cycle or Has Cycle on a second line accordingly. Hence, if the input been:

java TopSort 1 2 1 3 2 3

The output should be:

1 2 3
No Cycle

Point Breakdown